1. Field of the Invention
The present invention relates to a device for effectively processing a run-length consisting of null coefficients (i.e., the content in a data block is 0) of a Huffman encoding system in an entropy encoding portion of a picture encoding device.
2. Description of the Prior Art
FIG. 22 is a block diagram showing a conventional picture encoding device comprising an input terminal 1 to which picture data consisting of 8.times.8 pixel blocks is inputted, a discrete cosine conversion portion (DCT) 2, a zigzag conversion portion 3, a quantization portion 4, a quantization table 5, an entropy encoding portion 6, an encoding table 7, and an output terminal 8 from which parameter and encoded data are outputted.
The operation of the conventional picture encoding device is now explained. First, picture data is inputted from the picture data input terminal 1, for example, in a form of an 8-bit-length component picture P.sub.xy (x, y=0, 1, 2, 3 . . . , 7). The inputted picture data is transmitted to the discrete cosine conversion portion 2, where a two-dimensional discrete cosine conversion is carried out on each of the divided 8.times.8 pixel blocks P.sub.xy. As a result of the two-dimensional discrete cosine conversion, sixty-four (=8.times.8) coefficients S.sub.UV are obtained. The sixty-four DCT coefficients S.sub.UV obtained as a result of the two-dimensional discrete cosine conversion are inputted into the quantization portion 4, where each DCT coefficient S.sub.UV is divided by the value Q.sub.UV in the quantization table 5. The quantized sixty-four coefficients R.sub.UV are transmitted to the zigzag conversion portion 3 where serial-order coefficients are permuted into a zigzag order. The zigzag-order sixty-four coefficients R.sub.UV are then transmitted to the entropy encoding portion 6 where the sixty-four coefficients are encoded according to a Huffman encoding system, using the encoding table 7. Then, the encoded data is outputted in a certain byte unit (for example, 16 bits in length) from the output terminal 8.
The two-dimensional discrete cosine conversion is carried out on a component picture P.sub.xy (x, y=0, 1, 2, 3 . . . , 7) consisting of 8.times.8 pixels inputted into the input terminal 1 in the DCT 2. As a result, components S.sub.UV as shown by equation (1) are obtained. ##EQU1## where x, y=the position of a pixel in a block
u, v=the position of a DCT coefficient ##EQU2##
As shown in FIG. 23, the DCT coefficients S.sub.UV consist of S.sub.00, a DC (direct current) component, and of S.sub.01 -S.sub.77 AC (alternate current) components. The coefficient S.sub.00 is the largest component and the AC components have a very small value compared with the S.sub.00 coefficient.
The DCT coefficient S.sub.UV is inputted into the quantization portion 4. The DCT coefficients S.sub.UV are divided using the value Q.sub.UV in the quantization table 5 in the quantization portion 4. In other words, the quantized DCT coefficients R.sub.UV are derived from the following equation. EQU R=round (S.sub.UV /Q.sub.UV)
The round function converts the calculated result of S.sub.UV /Q.sub.UV to the closest integer. Accordingly, by setting the value Q.sub.UV in the quantization table so that the two-dimensional numbers U and V become large in proportion to the value of U and V, respectively, most of the AC coefficients become 0 when the degree is large.
The operation of the entropy encoding portion 6, which is a characteristic of a picture encoding device, is explained in detail. In FIG. 22, sixty-four coefficients R.sub.UV comprising a DC coefficient (R.sub.00) and the AC coefficients (except R.sub.00), outputted from the quantization portion 4, are transmitted to the entropy encoding portion 6 via the zigzag conversion portion 3. In the entropy encoding portion 6, a different encoding system is applied to the DC coefficient (R.sub.00), representing a mean value of 8.times.8 pixels, and the AC coefficients (except R.sub.00), respectively. The following explanation is given with respect to these different encoding systems.
FIG. 24 is a block diagram for grouping the DC coefficient R.sub.00. In FIG. 24, a DC differentiator 62 carries out a subtraction to derive a difference between the DC coefficient R.sub.00, inputted from the quantization portion 4, and a preceding DC coefficient R.sub.00, delayed by a block delay portion 61. The difference is transmitted to the grouping unit 9. As FIG. 25 shows, the difference between the DC coefficient (DC.sub.i) for a block (i) of the current DC component (for example, one of R, G, B in case of a color signal) and the DC coefficient (DC.sub.i-1) for a block (i-1) of the corresponding component encoded just before the block (i) is calculated by the DC differentiator 62, as a differential value (.DELTA.DC.sub.i =(DC.sub.i)-(DC.sub.i-1)). Since the mean value between two adjacent blocks does not change significantly often, except in some peculiar cases such as computer graphics, the differential value between the current DC coefficient and the preceding DC coefficient converges around zero. Accordingly, by encoding such differences calculated in this way, highly-efficient encoding is achieved.
The differential value of the DC coefficient calculated by the DC differentiator 62 is inputted to the grouping unit 9, where the group to which the differential value belongs is obtained, using the table of FIG. 29. The output from the grouping unit 9 represents the DC coefficient by a group number (S) and an additional bit (A). The additional bit (A) is a value indicating the order of the differential value in the group. In group 3 of FIG. 29, for example, the number of additional bits is three, and the DC differential value takes one of the following eight values, -7, -6, -5, -4, 4, 5, 6, 7, to which respective additional bits 000, 001, 010, 011, 100, 101, 110, 111 are allotted. In this way, the grouping unit 9 outputs the group number (S) and the additional bit (A). For example, if a DC coefficient is four, the value of the group number (S) is three (0011 in binary), and the value of the additional bit is four (0100 in binary) according to the table of FIG. 29. This group number (S) and the additional bit (A), the outputs from this grouping unit 9, are encoded by a one-dimensional Huffman encoding portion 65 in FIG. 28. The value of the group number (S) is referred to as DC* in the following description.
FIG. 26 is a block diagram showing a grouping of AC coefficients. The AC coefficients are permuted into a one-dimensional order, for example, AC.sub.01, AC.sub.10, AC.sub.20 . . . , AC.sub.75, AC.sub.66, AC.sub.77 by a zigzag scanning portion 91. AC.sub.01 represents an AC value with zigzag coordinates (0, 1). FIG. 27 is a diagram showing how zigzag scanning is carried out. Each of the AC coefficients permuted into one-dimensional order by the zigzag scanning portion 91 is determined in the judgement portion 92 to be zero or other than zero. If the AC coefficient is zero, the continuous number of zeros in the AC coefficient is counted in the run-length counter 93, and the count is outputted as a run-length (N). For example, if an AC coefficient comprises five continuous zeros, the run-length (N) is five (0101 in binary), and if an AC coefficient comprises fourteen continuous zeros, the run-length (N) is fourteen (1110 in binary).
If the AC coefficient is other than zero, the grouping portion 94 in FIG. 26 generates a group number (S) and an additional bit (A) by the same method as a DC coefficient is calculated. A group to which an AC coefficient belongs is determined according to the table of FIG. 31. The additional bit (A) is a value indicating the order of the AC coefficient in the group. For example, if an AC coefficient is fifteen, the group number is four. In group 4, the number of additional bits is four; in other words, the AC coefficient which belongs to the group 4 may take any one of the sixteen values of -15, -14 . . . , -8, 8, 9 . . . , 14, 15, which are represented by four bits. The additional bits 0000, 00001 . . . , 1110, 1111 are allotted to -15, -14 . . . , 14, 15, respectively. In this way, the group number (S) and the additional bit (A) are outputted from the grouping portion 94. Accordingly, the additional bit (A) for the AC coefficient 15 is fifteen (1111 in binary).
The group number (S), outputted from the grouping portion 94, and the run-length (N), outputted from the run-length counter 93, are Huffman-encoded by a two-dimensional Huffman encoding portion 95 and an AC encoding table portion 96 in the Huffman encoding portion 12, as explained below.
FIG. 28 is a block diagram showing a circuit for carrying out grouping and Huffman encoding on the DC coefficient and the AC coefficients. In FIG. 28, the DC grouping unit 9a is the same as in FIG. 24, and the AC grouping unit 9b is the same as in FIG. 26.
The operation of the Huffman encoding portion 12 is explained briefly. In FIG. 28, a one-dimensional Huffman encoding portion 65, a DC encoding table portion 66, and a DC additional bit coupling portion 67 constitute an encoding portion for DC coefficients, and two-dimensional Huffman encoding portions 95, an AC encoding table portion 96, and AC additional bit coupling portion 97 constitute an encoding portion for AC coefficients. A DC encoding signal and an AC encoding signal are coupled in a coupling circuit 68.
The encoding of a DC coefficient is explained below. The group number (S) (DC*) and the additional bit (A) are obtained in the DC grouping unit 9a. The group number (S) is encoded in the one-dimensional Huffman encoding portion 65, which carries out one-dimensional Huffman encoding on the group number (S) using a DC encoding table in the DC encoding table portion 66. The DC code (simply referred to as DC below) is then outputted.
FIG. 30 is a diagram showing an example of one-dimensional Huffman encoding. For example, if the group number (S)=4 is inputted into a one-dimensional Huffman encoding portion 65, the encoded DC code is 1110 after the one-dimensional Huffman encoding is carried out. The output 1110 from the one-dimensional Huffman encoding portion 65 is coupled with the additional bit 100 from the grouping unit 9a in the DC additional coupling portion 67 and becomes 1110100 (DC code+additional bits). As shown in FIG. 30, in a Huffman encoding system, since a signal can be transmitted by fewer code bits if the DC differential value is smaller, the transmission of a signal with a small DC differential value is highly efficient.
The encoding of AC coefficients is explained below. In FIG. 28, the group number (S) from the grouping unit 9b and a run-length (N) from the run-length counter 93 are encoded by the two-dimensional Huffman encoding portion 95 and the AC encoding table 96 in the Huffman encoding portion 12, where Huffman encoding is carried out on the group number (S) and the run-length (N). An additional bit (A) is added to the encoded value in the AC additional bit coupling portion 97, and then an encoded AC code is outputted. The two-dimensional encoding is explained in the following specific example.
Referring to FIG. 33, the operation is explained in respect to an example when sixty-four block signals are inputted into a circuit shown in FIG. 28, wherein the sixty-four bit signals include a DC coefficient (R.sub.00) having the differential value of four, outputted from the zigzag conversion portion 3 in FIG. 22, an AC coefficient (R.sub.UV) which includes four null coefficients of zero value, one AC coefficient (AC 1, value=10), sixteen null coefficients of zero value, three null coefficients of zero value, one AC coefficient (AC 2, value=3), and thirty-eight null coefficients of zero value.
The DC coefficient is grouped in the grouping unit 9a and outputted as a group number (S). The value of the group number (S) is referred to as DC* below. In this example, since the differential value is assumed to be four, the group number (S) is three, the number of the additional bits is three, and the number of the additional bits (A)=100, according to FIG. 29. This group number (S)=3 and the number of additional bits (A)=100 are encoded, and a one-dimensional Huffman-encoded signal="01101001", i.e., code word (=110)+the number of the additional bit (A)=100, is obtained.
On the other hand, each of the AC coefficients is grouped one by one in the grouping unit 9b, and the run-length (N), which indicates the length of a continuous number of zero coefficients, and the group number (S) following the run-length (N), which indicates the size of a coefficient value except zero, are coupled and encoded by the two-dimensional Huffman encoding portion 95 and the AC encoding table 96. The encoded two-dimensional Huffman code is added to the additional bit and outputted from the AC additional bit coupling portion 97.
In this example, four null coefficients of zero value are inputted as a run-length (N=4) into the two-dimensional Huffman encoding portion 95. The next AC coefficient, AC1 (value 10), is also inputted into the two-dimensional Huffman encoding portion 95. Since the value of the AC coefficient is ten, the group number (S) is four according to FIG. 31. Since the value ten of the effective coefficient is ranked 11th from the smallest, the additional bit is 1010. In the two-dimensional Huffman encoding, as described above, since the null coefficient (N) is four and the group number (S) is four, N/S is 4/4. Accordingly, two-dimensional Huffman encoding is carried out using an AC encoding table portion 96 (FIG. 32), which corresponds to N/S (4/4) in the two-dimensional Huffman encoding portion 95 in the Huffman encoding portion 12. After the additional bit is added, a two-dimensional Huffman encoding signal "11111111100110001010" is obtained.
The next sixteen null coefficients are counted by the run-length counter 93, and a count value of fifteen (1111 in binary) is outputted. This count value fifteen and the next zero value are encoded by the two-dimensional Huffman encoding portion 95, and a ZRL* is outputted. Since this ZRL* comprises a combination of a run-length (N) of fifteen and an effective coefficient of zero, an N/S signal is F/O, and an encoded signal ZRL="1111111010" is obtained from the AC encoding table of FIG. 32.
According to FIG. 31, the run-length (N) for the portion comprising three null coefficients and one AC2 (value=3) is three, the group number (S) is two, and the additional bit is three (11 in binary). Accordingly, the N/S signal is 3/2, and an encoded signal "11111000" is obtained from the AC encoding table of FIG. 32, which is outputted from the two-dimensional Huffman encoding portion 95. This encoded signal "11111000" is coupled with an additional bit in the AC additional bit coupling portion 97, and outputted as "1111100011".
In case the number of null coefficients is thirty-eight, since one ZRL* is allotted for every continuous number of sixteen null coefficients, two ZRL*s are continuously outputted from the two-dimensional Huffman encoding portion 95. As seen from the AC encoding table of FIG. 32, two encoded signals ZRL "111111010" for the respective two ZRL*s are continuously outputted. Since thirty-two zeros are used for two ZRL*s, an EOB* is allotted for the remaining six zeros. The EOB* code is a code which is outputted from the grouping unit 9 immediately after the code for the last effective coefficient, when the last AC coefficient AC.sub.77 is zero. This EOB* code is represented, for example, by "00" in binary as shown in the AC encoding table of FIG. 32.
The group number (S) designates the group to which an effective coefficient belongs, as described above, and an additional bit is used to indicate a specific value in the group. If the last AC coefficient (AC.sub.77) in the block is zero, an EOB* (End of Block) code is added immediately after the code for the last effective coefficient so that encoding of the block is completed. If the last AC coefficient (AC.sub.77) in the block is other than zero, no EOB* code is added. In the case of the run-length consisting of at least sixteen null coefficients, a ZRL* (Zero Run Length) code, indicating sixteen null coefficients in continuous number is outputted successively until the number of the null coefficients in the run-length becomes less than or equal to fifteen, and the remaining run-length N is then encoded. In a Huffman encoding system, encoding is carried out so that as many ZRL* codes are generated as possible so that a picture signal is compressed. Therefore, after the compression, the ZRL* code must be deleted. That is, in an entropy encoding portion of a conventional picture encoding device, if more than sixteen continuous null coefficients are received, multiple ZRL* codes are outputted. After the ZRL* codes are outputted, if an EOB* code is outputted, corresponding to null coefficients without an effective coefficient, ZRL* codes that have already been outputted should be deleted.
However, since the ZRL* codes have been already grouped and transmitted to the next stage, deletion of such ZRL* codes is difficult. Moreover, unnecessary ZRL* codes between an effective coefficient and an EOB* are dealt with as codes and Huffman-encoding is carried out on the unnecessary ZRL* codes, making the encoding efficiency worse. In order to avoid dealing with the unnecessary ZRL* codes, encoding processing of the ZRL* codes should be stopped before the Huffman encoding, retarding encoding processing speed.
The object of the present invention is to provide a picture encoding device for effectively deleting the ZRL* codes outputted before the EOB* code and before Huffman encoding.